def lcs_length(X,Y):
    m=len(X)
    n=len(Y)
    c=[[0]*(n+1) for i in xrange(m+1)]
    for i in xrange(m):
        for j in xrange(n):
            if X[i]==Y[j]:
                c[i+1][j+1]=c[i][j]+1
            elif c[i][j+1]>=c[i+1][j]:
                c[i+1][j+1]=c[i][j+1]
            else:
                c[i+1][j+1]=c[i+1][j]
    return c
def do_print_lcs(c,X,Y):
    m=len(X)
    n=len(Y)
    print_lcs_without_b(c,X,Y,m-1,n-1)
def print_lcs_without_b(c,X,Y,i,j):
    if i==-1 or j==-1:
        return
    if X[i]==Y[j]:
        print_lcs_without_b(c,X,Y,i-1,j-1)
        print X[i],
    elif c[i][j+1]>=c[i+1][j]:
        print_lcs_without_b(c,X,Y,i-1,j)
    else:
        print_lcs_without_b(c,X,Y,i,j-1)
if __name__=='__main__':
    from pprint import pprint
    X='ABCBDAB'
    Y='BDCABA'
    print 'X:',X
    print 'Y:',Y
    c=lcs_length(X,Y)
    print 'c:'
    pprint(c)
    print 'LCS:',
    do_print_lcs(c,X,Y)
